package top.hkyzf.study.leetcode.array;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhufeng
 * @version 1.0
 * @date 2022-3-6 23:07
 */
public class 适合打劫银行的日子_2100 {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        List<Integer> result = new ArrayList<>();
        for (int i = time; i < security.length - time; i++) {
            if (check(security, i, time)) {
                result.add(i);
            }
        }
        return result;
    }

    private boolean check(int[] security, int index, int time) {
        for (int i = index+1; i <= index+time; i++) {
            if (security[i-1] > security[i]) {
                return false;
            }
        }
        for (int i = index-1; i >= index-time; i--) {
            if (security[i+1] > security[i]) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> goodDaysToRobBank1(int[] security, int time) {
        int n = security.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; i++) {
            if (security[i] <= security[i-1]) {
                left[i] = left[i-1] + 1;
            }
            if (security[n-i-1] <= security[n-i]) {
                right[n-i-1] = right[n-i] + 1;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (left[i] >= time && right[i] >= time) {
                result.add(i);
            }
        }
        return result;
    }

    @Test
    public void testGoodDaysToRobBank () {
        int[] security = {5,3,3,3,5,6,2};
        int time = 2;
        System.out.println(goodDaysToRobBank1(security, time));
    }
}
